import java.util.Stack;

public class Partition {

    public ListNode partition(ListNode pHead, int x) {

        // write code here

        ListNode cur = pHead;

        ListNode prev = null;

        Stack<Integer> stack = new Stack<>();

        while (cur != null) {

            if (cur.val < x) {

                stack.push(cur.val);

                if (cur == pHead) {

                    pHead = pHead.next;

                    cur = pHead;

                } else {

                    prev.next = cur.next;

                    cur = cur.next;

                }


            } else {

                prev = cur;

                cur = cur.next;

            }

        }

        while (!stack.empty()) {

            ListNode newNode = new ListNode(stack.pop());

            newNode.next = pHead;

            pHead = newNode;

        }

        return pHead;

    }
}